package ds.list;

// 链表
public class MyLinkedList<T> implements IList<T> {
    private static class Node<T> {
        public T data;
        public Node<T> next;
        public Node<T> prev;
        public Node(T data) {
            this.data = data;
        }

    }

    // 哨兵位头节点
    private final Node<T> head = new Node<T>(null);
    private int valSize;

    public MyLinkedList() {
        head.next = head;
        head.prev = head;
        valSize = 0;
    }

    //头插法
    public void addFirst(T data) {
        Node<T> newNode = new Node<>(data);
        if (isEmpty()) {
            head.next = newNode;
            newNode.prev = head;
            head.prev = newNode;
            newNode.next = head;
        } else {
            Node<T> cur = head.next;
            head.next = newNode;
            newNode.prev = head;
            newNode.next = cur;
            cur.prev = newNode;
        }

        valSize++;
    }

    //尾插法
    public void addLast(T data) {
        if (isEmpty()) {
            addFirst(data);
        } else {
            Node<T> newNode = new Node<>(data);
            Node<T> cur = head.next;
            while (cur.next != head) {
                cur = cur.next;
            }
            cur.next = newNode;
            newNode.prev = cur;
            newNode.next = head;
            head.prev = newNode;
        }
        valSize++;
    }

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,T data) {

    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(Object key) {
        return false;

    }

    //删除第一次出现关键字为key的节点
    public boolean remove(Object key) {
        return false;
    }

    //头删
    public boolean removeFirst() {
        return false;

    }

    //尾删
    public boolean removeLast() {
        return false;

    }

    //删除所有值为key的节点
    public boolean removeAllKey(Object key) {
        return false;

    }

    // 删除下表为index的节点
    public boolean remove(int index) {
        return false;

    }

    //得到单链表的长度，如果链表很长，可以定义一个记录数据个数的整型变量，提高效率
    public int size() {
        return valSize;
    }

    public boolean isEmpty() {
        return head.next == head;
    }

    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        Node<T> cur = head.next;
        while (cur != head) {
            if (cur.next == head) {
                stringBuilder.append(cur.data);
            } else {
                stringBuilder.append(cur.data);
                stringBuilder.append(", ");
            }
            cur = cur.next;
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }
}
